from trees import get_distance

def build_kdtree(objects, depth = 0):
    size = len(objects)

    if size < 1: # если размер меньше 1, то объектов нет
        return None
    # выбор оси координат для сортировки и нахождения медианы
    axis = depth % 2 # если число четное, то сортировка по оси x, иначе по y
    # сортировка объектов
    sorted_objects = sorted(objects, key = lambda val : val.geometry['coordinates'][axis])

    return { # возвращение словаря и его заполнение через рекурсию
        'id' : sorted_objects[size // 2].id, # id медианного объекта
        'geometry' : sorted_objects[size // 2].geometry, # геометрия медианного объекта
        'left' : build_kdtree(sorted_objects[:size // 2], depth + 1), # рекурсивный вызов функции для левой части от меданы
        'right' : build_kdtree(sorted_objects[size // 2 + 1:], depth + 1) # рекурсивный вызов функции для правой части от меданы
    }

def kdtree_closest_point(root, defined_object, depth=0, best=None): # алгоритм нахождения ближайшей точки
    if root is None: # если корня не существует
        return best # возвращаем наилучший объект

    axis = depth % 2 # получение значения глубины, которое отвечает за выбор оси координат
    # по умолчанию следующая ветка и следующий наилучший объект - пустые
    next_best = None
    next_branch = None
    # если наилучший объект пуст или его расстояние до заданного объекта больше, чем у текущего узла
    if best is None or get_distance(defined_object, best['geometry']['coordinates']) > get_distance(defined_object, root['geometry']['coordinates']):
        next_best = { # присваиваем значения текущего узла в следующий наилучший объект
            'id': root['id'], 
            'geometry' : root['geometry'],
            'distance' : get_distance(defined_object, root['geometry']['coordinates'])
        }
    else: # присваиваем значения текущего наилучшего объекта в следующий наилучший объект
        next_best = best
    # если по текущей оси координат заданный объект меньше текущего узла
    if defined_object[axis] < root['geometry']['coordinates'][axis]:
        next_branch = root['left'] # установка левого потомка текущего узла в качестве следующего узла
    else:
        next_branch = root['right'] # установка правого потомка

    return kdtree_closest_point(next_branch, defined_object, depth + 1, next_best) # рекурсивный обход по дереву, пока программа не достигнет листа

def get_closest_object_from_kdtree(objects): # вычисление объекта с наименьшей дистанцией до заданного
    if len(objects) < 2:
        return objects[0]
    
    min = objects[0]

    for value in objects:
        if min['distance'] > value['distance']:
            min = value
    
    return min

def get_all_line_values_from_kdtree(root, line, coordinates):
    
    if root == None:
        return

    if line['id'] == root['id']:
        coordinates.append(root['geometry']['coordinates'])
    
    get_all_line_values_from_kdtree(root['left'], line, coordinates)
    get_all_line_values_from_kdtree(root['right'], line, coordinates)

    return coordinates